#ifndef HEAPSORT_HPP_
#define HEAPSORT_HPP_

#include <cmath>
#include <iostream>

#include "./heap-node.hpp"
#include "./pilha.hpp"
#include "./error.h"

/** Classe Heapsort
 * Implementa��o gen�rica do algoritmo de ordena��o heapsort. 
 * � necessario que o dado a ser inserido deve ter os operadores >. <. <= e >= . 
 * 
 * 
 * @author Dizus
 * 
 */
template<class T>
class heapsort
{
public:

	heapsort();

	~heapsort();

	void
	addNode( const T&);

	void
	addStack( pilha<T>);

	void
	clear();

	T
	getSmaler();

	const bool
	isEmpty();

protected:
	
	void
	setNextAvailable();

	T
	pop();

private:

	void
	filterUp( heapNode<T>* );

	void
	filterDown();

	void
	setCapacity();

	heapNode<T>*
	getLast( const bool );

	const bool
	canGoDown( heapNode<T>* );

	const unsigned short int
	isDaddyBigger( heapNode<T>* );

	void
	swapNodes( heapNode<T>* , heapNode<T>* );

	heapNode<T>*
	root;
	
	heapNode<T>*
	nextAvailable;

	int
	nodeCount;
	
	double
	capacity;
	
	double
	levels;
	
};

/*****************************************
 * 
 * Implementations 
 * 
 * ***************************************/

template<class T>
heapsort<T>::heapsort()
{
	this->root = 0;
	this->nextAvailable = 0;
	this->nodeCount = 0;
}

template<class T>
heapsort<T>::~heapsort()
{

}

template<class T> void
heapsort<T>::addNode(const T& _info)
{
	heapNode<T>*
	newNode = new heapNode<T>(_info);

	if (this->root == 0)
	{
		this->root = newNode;
		this->nextAvailable = newNode;
	}
	else
	{
		if (this->nextAvailable->getFirstSon() == 0)
		{
			this->nextAvailable->setFirstSon( newNode );
			newNode->setDaddy( this->nextAvailable);
		}
		else
		{
			this->nextAvailable->setSecSon( newNode );
			newNode->setDaddy( this->nextAvailable );
		}
	}
	this->filterUp( newNode );

	this->nodeCount++;

	this->setNextAvailable();
}

/** void addStack (const pilha<T>& _stack)
 * 
 * Insere os elementos de uma pilha na �rvore do heap.
 * 
 */
template<class T> void
heapsort<T>::addStack( pilha<T> _stack)
{
	while (! _stack.isEmpty() )
	{
		this->addNode( _stack.getInfo() );
		_stack.pop();
	}
}

template<class T> void
heapsort<T>::clear()
{
	while (! this->isEmpty() )
		this->pop();
}

template<class T> const bool
heapsort<T>::isEmpty()
{
	if ( this->root == 0 )
		return true;
	return false;
}

template<class T> T
heapsort<T>::getSmaler()
{
	return this->pop();
}
/******************************
 * 
 * 	Protected methods
 * 
 * ****************************/

template<class T> void
heapsort<T>::setNextAvailable()
{
	if ( this->nodeCount >= 3 && this->canGoDown( this->nextAvailable ) )
	{
		this->nextAvailable = this->getLast(false);
	}
	else if ( this->nodeCount < 3 && this->nodeCount > 0 )
		this->nextAvailable = this->root;
}

template<class T> T
heapsort<T>::pop()
{
	heapNode<T>*
	returnNode = this->root;
	
	if ( this->root->getFirstSon()!= 0)
	{
	
		this->root = this->getLast( true );
	
		if ( this->root->getDaddy()->getFirstSon() == this->root )
		{
			this->root->getDaddy()->setFirstSon(0);
		}
		else
		{
			this->root->getDaddy()->setSecSon(0);
		}
		
		this->root->setDaddy(0);
		this->root->setFirstSon( returnNode->getFirstSon() );
		this->root->setSecSon( returnNode->getSecSon() );
	
		if (this->root->getFirstSon() != 0)
			this->root->getFirstSon()->setDaddy( this->root );
	
		if (this->root->getSecSon() != 0)
			this->root->getSecSon()->setDaddy( this->root );
		
	
		this->filterDown();
	
		this->nodeCount--;
	}
	else
	{
		returnNode = this->root;
		this->root = 0;
	}
	
	T
	retInfo = returnNode->getInfo();
		
	delete returnNode;
	
	return retInfo;
}

/*************************************
 * 
 *  private methods
 * 
 * ***********************************/

template<class T> void
heapsort<T>::filterUp(heapNode<T>* _node)
{
	if ( _node != 0 && _node->getDaddy() != 0 )
	{
		heapNode<T>*
		daddyNode = _node->getDaddy();

		while( _node->getDaddy() != 0 && daddyNode->getInfo() > _node->getInfo() )
		{
			this->swapNodes( _node, daddyNode);

			daddyNode = _node->getDaddy();
		}
	}
}

template<class T> void
heapsort<T>::filterDown()
{
	heapNode<T>*
	cursor = this->root;
	
	unsigned short int 
	test;
	
	while( this->canGoDown( cursor ) && ( test = this->isDaddyBigger( cursor ) ) )
	{
			switch (test)
			{
			case 1:
				this->swapNodes( cursor->getFirstSon(), cursor );
				this->filterUp( cursor->getSecSon() );
				break;
			case 2:
				this->swapNodes(cursor->getSecSon() , cursor );
				this->filterUp( cursor->getFirstSon() );
				break;
			}
			
	}
}

/** Metodo Privado: getLast
 * 
 * Metodo que navega na arvora a procura do ultimo elemennto inserido ou do 
 * proximo elemento que pode receber filhos.
 * 
 *  @return: ponteiro para noh desejado
 * 
 *  @params:
 *    * const bool _choice: 
 *      true - para o ultimo elemento inserido
 *      false - para o proximo elemento a receber filhos 
 * 
 */
template<class T> heapNode<T>*
heapsort<T>::getLast( const bool _choice)
{
	this->setCapacity();

	double
	subTreeCapacity = this->capacity;

	double
	subTreeNodeCount = this->nodeCount;

	double
	interactions = 1;

	heapNode<T>*
	cursor = this->root;

	for (double lineCounter = this->levels ; (lineCounter > 0) && ( cursor->getFirstSon() != 0 || cursor->getSecSon() != 0 ) ; lineCounter--)
	{

		if ( subTreeNodeCount == subTreeCapacity) //nivel cheio
		{
			if ( _choice == false )
			{
				cursor = cursor->getFirstSon();
				subTreeNodeCount = subTreeNodeCount - ( subTreeNodeCount - pow( 2,this->levels ) ) - 1;
			}
			else
			{
				cursor = cursor->getSecSon();
				subTreeNodeCount = subTreeNodeCount - ( subTreeNodeCount - pow( 2,this->levels ) ) - 1;
				
			}
		}
		else if ( subTreeNodeCount == subTreeCapacity - pow( 2,this->levels - 1 )/interactions )  //exatamente na metade
		{
			if ( _choice == false )
			{
				cursor = cursor->getSecSon();
				subTreeNodeCount = subTreeNodeCount - ( subTreeNodeCount - pow( 2,this->levels - 1 ) ) - 1;
			}
			else
			{
				cursor = cursor->getFirstSon();
				subTreeNodeCount = subTreeNodeCount - ( subTreeNodeCount - pow( 2,this->levels ) ) - 1;
			}
		}
		else if ( ceil((subTreeNodeCount-1)/2) < ceil((subTreeCapacity -1 )/2) )  //menos da metade...
		{
			cursor = cursor->getFirstSon();
			subTreeNodeCount = subTreeNodeCount - ( subTreeNodeCount - pow(2,this->levels - 1 ) ) - 1;
		}
		else  // mais que a metade
		{
			cursor = cursor->getSecSon();
			subTreeNodeCount = subTreeNodeCount - ( subTreeNodeCount - pow(2,this->levels -1 ) ) - 1;
		}




		subTreeCapacity--;
		subTreeCapacity/=2;
		
		interactions++;
	}

	return cursor;
}

template<class T> void
heapsort<T>::setCapacity()
{
	this->levels = floor ( log10(this->nodeCount) / log10(2) );

	this->capacity = 0;

	for( double counter = this->levels; counter > 0; counter-- )
	{
		this->capacity += pow(2,counter);
	}

	this->capacity++;
}

template<class T> const bool
heapsort<T>::canGoDown( heapNode<T>* _node )
{
	if ( _node->getFirstSon() != 0 && _node->getSecSon() != 0 )
		return true;
	return false;
}

template<class T> const unsigned short int
heapsort<T>::isDaddyBigger( heapNode<T>* _node )
{
	bool
	isFirst = false;

	bool
	isSecond = false;

	if ( _node->getFirstSon()->getInfo() < _node->getInfo() )
		isFirst = true;
	if ( _node->getSecSon()->getInfo() < _node->getInfo() )
		isSecond = true;
	
	if ( isFirst == true && isSecond == true )
	{
		if ( _node->getFirstSon()->getInfo() < _node->getSecSon()->getInfo() )
		{
			return 1;
		}
		else
			return 2;
	}
	else if (isFirst == true)
	{
		return 1;
	}
	else if ( isSecond == true )
	{
		return 2;
	}
	else
		return 0;
}

template<class T> void
heapsort<T>::swapNodes( heapNode<T>* _node, heapNode<T>* _daddyNode)
{
	heapNode<T>*
	helpNodeFSon;

	heapNode<T>*
	helpNodeSSon;

	heapNode<T>*
	helpNodeDaddy;
	
	helpNodeFSon = _node->getFirstSon();
	helpNodeSSon = _node->getSecSon();

	helpNodeDaddy = _daddyNode->getDaddy();

	if ( _daddyNode->getFirstSon() == _node )
	{
		_node->setFirstSon( _daddyNode );
		_node->setSecSon( _daddyNode->getSecSon() );
	}
	else
	{
		_node->setSecSon( _daddyNode );
		_node->setFirstSon( _daddyNode->getFirstSon() );

	}
	_node->setDaddy( helpNodeDaddy );

	_daddyNode->setDaddy( _node );
	_daddyNode->setFirstSon( helpNodeFSon );
	_daddyNode->setSecSon( helpNodeSSon );

	if( helpNodeFSon != 0 )
		helpNodeFSon->setDaddy( _daddyNode );

	if( helpNodeSSon != 0 )
		helpNodeSSon->setDaddy( _daddyNode );

	if( helpNodeDaddy != 0 )
	{
		if( helpNodeDaddy->getFirstSon() == _daddyNode )
		{
			helpNodeDaddy->setFirstSon( _node );
		}
		else
		{
			helpNodeDaddy->setSecSon( _node );
		}
	}

	if( _node->getDaddy() == 0)
	{
		this->root = _node;
	}
}

#endif /*HEAPSORT_HPP_*/
